package com.le.tester.imooc.oldfairy.coding.sorting;

import org.junit.Test;

import java.util.Arrays;

/**
 * createTime：2023/5/23 14:01
 * description：合并排序,二分法
 */
public class MergeSort implements IMutableSorter {

    @Override
    public void sort(int[] arr) {
        mergeSort(arr, 0, arr.length);
    }

    //左闭右开
    private void mergeSort(int[] arr, int left, int right) {

        //n/2直到一个元素，递归终结
        if (right - left <= 1) {
            return;
        }
        //stack loop，先进后出
        int mid = (left + right + 1) / 2;
        //左边
        mergeSort(arr, left, mid);
        //右边
        mergeSort(arr, mid, right);


        //递归结束之后执行栈中元素
        merge(arr, left, mid, right);
    }

    //合并
    private void merge(int[] arr, int left, int mid, int right) {
        //左闭右开进行数组操作
        int[] leftArr = Arrays.copyOfRange(arr, left, mid + 1);
        int[] rightArr = Arrays.copyOfRange(arr, mid, right + 1);

        //给数组设置边界值
        leftArr[leftArr.length - 1] = rightArr[rightArr.length - 1] = Integer.MAX_VALUE;
        int i = 0;
        int j = 0;
        //遍历所需要的元素即可
        for (int k = left; k < right; k++) {
            if (leftArr[i] < rightArr[j]) {
                arr[k] = leftArr[i++];
            } else {
                arr[k] = rightArr[j++];
            }

        }
    }


    @Test
    public void testMergeSort() {

        this.mergeSort(new int[]{1, 2, 3, 5, 4, 8, 9, 256, 7, 8}, 0, 10);

    }
}
